import java.util.ArrayList;
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.HashMap;



/**
 * a collection of algorithims on nodes and graphs
 **/
public class Algorithms {

  public Algorithms() { }

  /**
   * uses depth first search to find a connection between from and to
   * @return Choice either nothing (indicating no connection) or the stack
   *         of nodes connecting the two nodes.
   **/
  public static <NI, LI> Choice<Stack<INode<NI, LI>>> DFS(INode<NI, LI> from, INode<NI, LI> to) {
    return DFSAcc(from, to, new Stack<INode<NI, LI>>());
  }

  private static <NI, LI> Choice<Stack<INode<NI, LI>>> DFSAcc(INode<NI, LI> from, INode<NI, LI> to, Stack<INode<NI, LI>> path) {
    // stuck in a cycle
    if(path.contains(from))
      return new Nothing<Stack<INode<NI, LI>>>();

    // this might be the next step in the path
    path.push(from);

    // we're there!
    if(from.equals(to))
      return new Something<Stack<INode<NI, LI>>>(path);

    // check all the nodes neighboring this one
    for(ILink<LI, NI> neighbor : from.getLinks()) {
      Choice result = DFSAcc(neighbor.getDestination(), to, path);
      if(result.isSomething())
        return result;
    }

    // nevermind, this wasn't it (we would've return'ed in the for loop)
    path.pop();
    return new Nothing<Stack<INode<NI, LI>>>();
  }

  /**
   * uses breadth first search to find a connection between origin and
   * terminus
   * @return Boolean true if there is a connection, false otherwise
   **/
  public static <NI, LI> Choice<LinkedList<INode<NI, LI>>> BFS(INode<NI, LI> origin, INode<NI, LI> terminus) {
    Queue<INode<NI, LI>> toCheck = new LinkedList<INode<NI, LI>>();
    ArrayList<INode<NI, LI>> seen = new ArrayList<INode<NI, LI>>();
    HashMap<INode<NI, LI>, INode<NI, LI>> steps = new HashMap<INode<NI, LI>, INode<NI, LI>>();
    toCheck.add(origin);

    while(!toCheck.isEmpty()) {
      INode<NI, LI> from = toCheck.remove();

      if(from.equals(terminus)) {
        INode<NI, LI> lastNodeSteppedTo = terminus;
        LinkedList<INode<NI, LI>> path = new LinkedList<INode<NI, LI>>();
        path.addFirst(lastNodeSteppedTo);

        while(!lastNodeSteppedTo.equals(origin)) {
          lastNodeSteppedTo = steps.get(lastNodeSteppedTo);
          path.addFirst(lastNodeSteppedTo);
        }
        return new Something<LinkedList<INode<NI, LI>>>(path);
      }

      seen.add(from);

      for(ILink<LI, NI> neighbor : from.getLinks()) {
        if(!seen.contains(neighbor.getDestination())) {
          toCheck.add(neighbor.getDestination());
          steps.put(neighbor.getDestination(), from);
        }
      }
    }

    return new Nothing<LinkedList<INode<NI, LI>>>();
  }
/*
  /**
   * uses a shortest path algorithm to find a connection between origin and
   * terminus
   * @return Choice either a Something containing the path or a Nothing
   *                representing no path found
   **
  public static <NI, LI> Choice<ArrayList<INode<NI, LI>>
    SP(Graph g, INode<NI, LI> origin, INode<NI, LI> terminus) {

    PriorityQueue<Pair<INode<NI, LI>, Double>> pq = initToInf(g.getNodes());
    HashMap<INode<NI, LI>, Double> distance = new ArrayList<Integer>();
    ArrayList<INode<NI, LI>> previousNode = new ArrayList<INode<NI, LI>>();

    while(!pq.isEmpty()) {

    }

  }


  // creates a priority queue of pairs of values, initializing all the right
  // hand sides of the pairs to positive infinity and the left hand sides are
  // taken from the collection c
  private static <E> PriorityQueue<Pair<E, Double>> initToInf(Collection<E> c) {
    Comparator<Pair<E, Double>> comp = new Comparator<Pair<E, Double>>(){
      int compare(Pair<E, Double> p1, Pair<E, Double> p2) { return p1.second.compareTo(p2.second); }
      boolean equals(Pair<E, Double> p1, Pair<E, Double> p2) { return p1.second.equals(p2.second); }};

    PriorityQueue<Pair<E, Double>> acc = new PriorityQueue<Pair<E, Double>>(c.size(), comp);
    for(E e : c)
      acc.add(new Pair(e, Double.POSITIVEINFINITY));
    return acc;
  }
  */

}

